package 剑指offer;

public class p55II平衡二叉树 {
    //平衡二叉树：如果二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。
    public boolean isBalanced(TreeNode root) {
        if (root==null) {
            return true;
        }

        //左子树高度
        int leftHeight=getHeight(root.left);
        //右子树高度
        int rightHeight=getHeight(root.right);

        //注意要记着判断 左右子树中的任意节点的左右子树高度差不超过 1
        return Math.abs(leftHeight-rightHeight)<2 && isBalanced(root.left) && isBalanced(root.right);
    }

    private int getHeight(TreeNode root) {
        if (root==null) {
            return 0;
        }

        int leftHeight = getHeight(root.left);
        int rightHeight=getHeight(root.right);
        return Math.max(leftHeight,rightHeight)+1;
    }
}
